﻿// 4546. 最大和加强加强版.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>

using namespace std;
/*

https://www.acwing.com/problem/content/4549/
https://vjudge.net/problem/HDU-1024

给定一个长度为 n 的整数序列 S1,S2,…,Sn。

我们规定函数 sum(i,j)=Si+…+Sj（1≤i≤j≤n）。

现在，给定一个整数 m
，你的任务是找到 m 个数对 (i,j)
，使得 sum(i1,j1)+sum(i2,j2)+sum(i3,j3)+…+sum(im,jm)
 的和尽可能大（ix≤iy≤jx或 ix≤jy≤jx 是不允许的）。

请你输出这个最大可能和。

输入格式
输入包含多组测试数据。

每组数据占一行，首先包含两个整数 m,n，随后包含 n 个整数 S1,S2,…,Sn。

输出格式
每组数据输出一行，一个整数，表示最大可能和。

数据范围
每个输入最多包含 10 组数据。
1≤n≤106
,
1≤m≤1000
,
每个输入的所有数据的 n×m相加之和不超过 5×107。
−32768≤Sx≤32767。

输入样例：
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
输出样例：
6
8


7 10 8 4 3 -7 8 1 -9 -10 -8 2
*/

//dp[x][y] 前x个数对 y结尾的最大可能和
//前y个数字 分为 x组

const int N = 1000010;
int dp[2][N][2];		//0表示当前数字不是最后一组中 1 表示当前数字是最后一组中
int n, m;
int arr[N];

int main()
{
	while (~scanf("%d %d", &m, &n)) {
		for (int i = 1; i <= n; i++) {
			scanf("%d", &arr[i]);
		}

		for (int i = 0; i < 2; i++) {
			for (int j = 0; j <= n; j++) {
				dp[i][j][0] = -0x3f3f3f3f;
				dp[i][j][1] = -0x3f3f3f3f;
				dp[0][j][0] = 0;
			}
		}

		int curr = 1; int prev = 0;
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				dp[curr][j][0] = -0x3f3f3f3f;
				dp[curr][j][1] = -0x3f3f3f3f;

				if (i <= j) {
					dp[curr][j][0] = max(dp[curr][j][0], max(dp[curr][j - 1][0], dp[curr][j - 1][1]));
					dp[curr][j][1] = max(dp[curr][j][1], max(dp[curr][j - 1][1] + arr[j], dp[prev][j][0] + arr[j]));

					/*if (dp[curr][j][0] >= 0) {
						cout << "i = " << i << ". j = " << j << ",0 , dp = " << dp[curr][j][0] << endl;
					}
					if (dp[curr][j][1] >= 0) {
						cout << "i = " << i << ". j = " << j << ",1 , dp = " << dp[curr][j][1] << endl;
					}*/
				}

			}


			swap(curr, prev);
		}

		printf("%d\n", max(dp[prev][n][0], dp[prev][n][1]));
	}



	return 0;
}

